/**
https://leetcode.cn/problems/snakes-and-ladders/description/
909. 蛇梯棋
 Medium, 方钊堉 2024.12.07
 BFS
 */

class Solution {
public:
    // 将一维 id 转换为二维坐标 (r, c)
    pair<int, int> idToRC(int id, int n) {
        int row = (id - 1) / n;
        int col = (id - 1) % n;
        if (row % 2 == 1) {
            col = n - 1 - col; // 如果行号是奇数，列号需要反转
        }
        return make_pair(n - 1 - row, col); // 返回转换后的坐标
    }

    int snakesAndLadders(vector<vector<int>>& board) {
        int steps = 0; // 记录步数
        queue<int> q; // BFS 队列
        unordered_set<int> seen; // 记录已访问的位置

        int n = board.size();
        q.push(1); // 从位置 1 开始
        seen.insert(1);

        while (!q.empty()) {
            ++steps; // 每处理一层，步数加 1
            int layerSize = q.size(); // 当前层的节点数量

            for (int i = 0; i < layerSize; ++i) {
                int current = q.front();
                q.pop();

                // 尝试掷骰子的每一种可能结果（1 到 6）
                for (int dice = 1; dice <= 6; ++dice) {
                    int next = current + dice;
                    if (next > n * n) break; // 超过最大位置，跳出循环

                    auto [row, col] = idToRC(next, n); // 获取下一个位置的坐标

                    // 如果有蛇或梯子，移动到指定位置
                    if (board[row][col] != -1) {
                        next = board[row][col];
                    }

                    // 如果到达终点，返回步数
                    if (next == n * n) {
                        return steps;
                    }

                    // 如果该位置未访问过，加入队列并标记为已访问
                    if (seen.count(next) == 0) {
                        seen.insert(next);
                        q.push(next);
                    }
                }
            }
        }

        return -1; // 无法到达终点，返回 -1
    }

private:
    queue<int> q; // BFS 队列
    unordered_set<int> seen; // 记录已访问的位置
};